home *** CD-ROM | disk | FTP | other *** search
/ SGI Freeware 1999 August / SGI Freeware 1999 August.iso / dist / samba.idb / usr / samba / src / source / ubiqx / ubi_BinTree.c.z / ubi_BinTree.c
Encoding:
C/C++ Source or Header  |  1998-10-28  |  42.5 KB  |  1,041 lines
  1. /* ========================================================================== **
  2.  *                              ubi_BinTree.c
  3.  *
  4.  *  Copyright (C) 1991-1997 by Christopher R. Hertel
  5.  *
  6.  *  Email:  crh@ubiqx.mn.org
  7.  * -------------------------------------------------------------------------- **
  8.  *
  9.  *  This module implements a simple binary tree.
  10.  *
  11.  * -------------------------------------------------------------------------- **
  12.  *
  13.  *  This library is free software; you can redistribute it and/or
  14.  *  modify it under the terms of the GNU Library General Public
  15.  *  License as published by the Free Software Foundation; either
  16.  *  version 2 of the License, or (at your option) any later version.
  17.  *
  18.  *  This library is distributed in the hope that it will be useful,
  19.  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  20.  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  21.  *  Library General Public License for more details.
  22.  *
  23.  *  You should have received a copy of the GNU Library General Public
  24.  *  License along with this library; if not, write to the Free
  25.  *  Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  26.  *
  27.  * -------------------------------------------------------------------------- **
  28.  *
  29.  * Log: ubi_BinTree.c,v
  30.  * Revision 2.5  1997/12/23 03:56:29  crh
  31.  * In this version, all constants & macros defined in the header file have
  32.  * the ubi_tr prefix.  Also cleaned up anything that gcc complained about
  33.  * when run with '-pedantic -fsyntax-only -Wall'.
  34.  *
  35.  * Revision 2.4  1997/07/26 04:11:10  crh
  36.  * + Just to be annoying I changed ubi_TRUE and ubi_FALSE to ubi_trTRUE
  37.  *   and ubi_trFALSE.
  38.  * + There is now a type ubi_trBool to go with ubi_trTRUE and ubi_trFALSE.
  39.  * + There used to be something called "ubi_TypeDefs.h".  I got rid of it.
  40.  * + Added function ubi_btLeafNode().
  41.  *
  42.  * Revision 2.3  1997/06/03 05:16:17  crh
  43.  * Changed TRUE and FALSE to ubi_TRUE and ubi_FALSE to avoid conflicts.
  44.  * Also changed the interface to function InitTree().  See the comments
  45.  * for this function for more information.
  46.  *
  47.  * Revision 2.2  1995/10/03 22:00:07  CRH
  48.  * Ubisized!
  49.  * 
  50.  * Revision 2.1  95/03/09  23:37:10  CRH
  51.  * Added the ModuleID static string and function.  These modules are now
  52.  * self-identifying.
  53.  * 
  54.  * Revision 2.0  95/02/27  22:00:17  CRH
  55.  * Revision 2.0 of this program includes the following changes:
  56.  *
  57.  *     1)  A fix to a major typo in the RepaceNode() function.
  58.  *     2)  The addition of the static function Border().
  59.  *     3)  The addition of the public functions FirstOf() and LastOf(), which
  60.  *         use Border(). These functions are used with trees that allow
  61.  *         duplicate keys.
  62.  *     4)  A complete rewrite of the Locate() function.  Locate() now accepts
  63.  *         a "comparison" operator.
  64.  *     5)  Overall enhancements to both code and comments.
  65.  *
  66.  * I decided to give this a new major rev number because the interface has
  67.  * changed.  In particular, there are two new functions, and changes to the
  68.  * Locate() function.
  69.  *
  70.  * Revision 1.0  93/10/15  22:44:59  CRH
  71.  * With this revision, I have added a set of #define's that provide a single,
  72.  * standard API to all existing tree modules.  Until now, each of the three
  73.  * existing modules had a different function and typedef prefix, as follows:
  74.  *
  75.  *       Module        Prefix
  76.  *     ubi_BinTree     ubi_bt
  77.  *     ubi_AVLtree     ubi_avl
  78.  *     ubi_SplayTree   ubi_spt
  79.  *
  80.  * To further complicate matters, only those portions of the base module
  81.  * (ubi_BinTree) that were superceeded in the new module had the new names.
  82.  * For example, if you were using ubi_AVLtree, the AVL node structure was
  83.  * named "ubi_avlNode", but the root structure was still "ubi_btRoot".  Using
  84.  * SplayTree, the locate function was called "ubi_sptLocate", but the next
  85.  * and previous functions remained "ubi_btNext" and "ubi_btPrev".
  86.  *
  87.  * This was not too terrible if you were familiar with the modules and knew
  88.  * exactly which tree model you wanted to use.  If you wanted to be able to
  89.  * change modules (for speed comparisons, etc), things could get messy very
  90.  * quickly.
  91.  *
  92.  * So, I have added a set of defined names that get redefined in any of the
  93.  * descendant modules.  To use this standardized interface in your code,
  94.  * simply replace all occurances of "ubi_bt", "ubi_avl", and "ubi_spt" with
  95.  * "ubi_tr".  The "ubi_tr" names will resolve to the correct function or
  96.  * datatype names for the module that you are using.  Just remember to
  97.  * include the header for that module in your program file.  Because these
  98.  * names are handled by the preprocessor, there is no added run-time
  99.  * overhead.
  100.  *
  101.  * Note that the original names do still exist, and can be used if you wish
  102.  * to write code directly to a specific module.  This should probably only be
  103.  * done if you are planning to implement a new descendant type, such as
  104.  * red/black trees.  CRH
  105.  *
  106.  *  V0.0 - June, 1991   -  Written by Christopher R. Hertel (CRH).
  107.  *
  108.  * ========================================================================== **
  109.  */
  110.  
  111. #include "ubi_BinTree.h"            /* Header for this module          */
  112. #include <stdlib.h>                 /* Standard C definitions.         */
  113.  
  114. /* ========================================================================== **
  115.  * Static data.
  116.  */
  117.  
  118. static char ModuleID[] = "ubi_BinTree\n\
  119. \tRevision: 2.5\n\
  120. \tDate: 1997/12/23 03:56:29\n\
  121. \tAuthor: crh\n";
  122.  
  123. /* ========================================================================== **
  124.  * Internal (private) functions.
  125.  */
  126.  
  127. static ubi_btNodePtr qFind( ubi_btCompFunc cmp,
  128.                             ubi_btItemPtr  FindMe,
  129.                    register ubi_btNodePtr  p )
  130.   /* ------------------------------------------------------------------------ **
  131.    * This function performs a non-recursive search of a tree for a node
  132.    * matching a specific key.  It is called "qFind()" because it is
  133.    * faster that TreeFind (below).
  134.    *
  135.    *  Input:
  136.    *     cmp      -  a pointer to the tree's comparison function.
  137.    *     FindMe   -  a pointer to the key value for which to search.
  138.    *     p        -  a pointer to the starting point of the search.  <p>
  139.    *                 is considered to be the root of a subtree, and only
  140.    *                 the subtree will be searched.
  141.    *
  142.    *  Output:
  143.    *     A pointer to a node with a key that matches the key indicated by
  144.    *     FindMe, or NULL if no such node was found.
  145.    *
  146.    *  Note:   In a tree that allows duplicates, the pointer returned *might
  147.    *          not* point to the (sequentially) first occurance of the
  148.    *          desired key.
  149.    * ------------------------------------------------------------------------ **
  150.    */
  151.   {
  152.   int tmp;
  153.  
  154.   while( p && (( tmp = ubi_trAbNormal((*cmp)(FindMe, p)) ) != ubi_trEQUAL) )
  155.     p = p->Link[tmp];
  156.  
  157.   return( p );
  158.   } /* qFind */
  159.  
  160. static ubi_btNodePtr TreeFind( ubi_btItemPtr  findme,
  161.                                ubi_btNodePtr  p,
  162.                                ubi_btNodePtr *parentp,
  163.                                char          *gender,
  164.                                ubi_btCompFunc CmpFunc )
  165.   /* ------------------------------------------------------------------------ **
  166.    * TreeFind() searches a tree for a given value (findme).  It will return a
  167.    * pointer to the target node, if found, or NULL if the target node was not
  168.    * found.
  169.    *
  170.    * TreeFind() also returns, via parameters, a pointer to the parent of the
  171.    * target node, and a LEFT or RIGHT value indicating which child of the
  172.    * parent is the target node.  *If the target is not found*, then these
  173.    * values indicate the place at which the target *should be found*.  This
  174.    * is useful when inserting a new node into a tree or searching for nodes
  175.    * "near" the target node.
  176.    *
  177.    * The parameters are:
  178.    *
  179.    *  findme   -  is a pointer to the key information to be searched for.
  180.    *  p        -  points to the root of the tree to be searched.
  181.    *  parentp  -  will return a pointer to a pointer to the !parent! of the
  182.    *              target node, which can be especially usefull if the target
  183.    *              was not found.
  184.    *  gender   -  returns LEFT or RIGHT to indicate which child of *parentp
  185.    *              was last searched.
  186.    *  CmpFunc  -  points to the comparison function.
  187.    *
  188.    * This function is called by ubi_btLocate() and ubi_btInsert().
  189.    * ------------------------------------------------------------------------ **
  190.    */
  191.   {
  192.   register ubi_btNodePtr tmp_p = p;
  193.   ubi_btNodePtr tmp_pp         = NULL;
  194.   int tmp_gender               = ubi_trEQUAL;
  195.   int tmp_cmp;
  196.  
  197.   while( tmp_p
  198.      && (ubi_trEQUAL != (tmp_cmp = ubi_trAbNormal((*CmpFunc)(findme, tmp_p)))) )
  199.     {
  200.     tmp_pp     = tmp_p;                 /* Keep track of previous node. */
  201.     tmp_gender = tmp_cmp;               /* Keep track of sex of child.  */
  202.     tmp_p      = tmp_p->Link[tmp_cmp];  /* Go to child. */
  203.     }
  204.   *parentp = tmp_pp;                /* Return results. */
  205.   *gender  = tmp_gender;
  206.   return( tmp_p );
  207.   } /* TreeFind */
  208.  
  209. static void ReplaceNode( ubi_btNodePtr *parent,
  210.                          ubi_btNodePtr  oldnode,
  211.                          ubi_btNodePtr  newnode )
  212.   /* ------------------------------------------------------------------ *
  213.    * Remove node oldnode from the tree, replacing it with node newnode.
  214.    *
  215.    * Input:
  216.    *  parent   - A pointer to he parent pointer of the node to be
  217.    *             replaced.  <parent> may point to the Link[] field of
  218.    *             a parent node, or it may indicate the root pointer at
  219.    *             the top of the tree.
  220.    *  oldnode  - A pointer to the node that is to be replaced.
  221.    *  newnode  - A pointer to the node that is to be installed in the
  222.    *             place of <*oldnode>.
  223.    *
  224.    * Notes:    Don't forget to free oldnode.
  225.    *           Also, this function used to have a really nasty typo
  226.    *           bug.  "oldnode" and "newnode" were swapped in the line
  227.    *           that now reads:
  228.    *     ((unsigned char *)newnode)[i] = ((unsigned char *)oldnode)[i];
  229.    *           Bleah!
  230.    * ------------------------------------------------------------------ *
  231.    */
  232.   {
  233.   register int i;
  234.   register int btNodeSize = sizeof( ubi_btNode );
  235.  
  236.   for( i = 0; i < btNodeSize; i++ ) /* Copy node internals to new node. */
  237.     ((unsigned char *)newnode)[i] = ((unsigned char *)oldnode)[i];
  238.   (*parent) = newnode;              /* Old node's parent points to new child. */
  239.   /* Now tell the children about their new step-parent. */
  240.   if( oldnode->Link[ubi_trLEFT] )
  241.     (oldnode->Link[ubi_trLEFT])->Link[ubi_trPARENT] = newnode;
  242.   if( oldnode->Link[ubi_trRIGHT] )
  243.     (oldnode->Link[ubi_trRIGHT])->Link[ubi_trPARENT] = newnode;
  244.   } /* ReplaceNode */
  245.  
  246. static void SwapNodes( ubi_btRootPtr RootPtr,
  247.                        ubi_btNodePtr Node1,
  248.                        ubi_btNodePtr Node2 )
  249.   /* ------------------------------------------------------------------------ **
  250.    * This function swaps two nodes in the tree.  Node1 will take the place of
  251.    * Node2, and Node2 will fill in the space left vacant by Node 1.
  252.    *
  253.    * Input:
  254.    *  RootPtr  - pointer to the tree header structure for this tree.
  255.    *  Node1    - \
  256.    *              > These are the two nodes which are to be swapped.
  257.    *  Node2    - /
  258.    *
  259.    * Notes:
  260.    *  This function does a three step swap, using a dummy node as a place
  261.    *  holder.  This function is used by ubi_btRemove().
  262.    * ------------------------------------------------------------------------ **
  263.    */
  264.   {
  265.   ubi_btNodePtr *Parent;
  266.   ubi_btNode     dummy;
  267.   ubi_btNodePtr  dummy_p = &dummy;
  268.  
  269.   /* Replace Node 1 with the dummy, thus removing Node1 from the tree. */
  270.   if( Node1->Link[ubi_trPARENT] )
  271.     Parent = &((Node1->Link[ubi_trPARENT])->Link[(int)(Node1->gender)]);
  272.   else
  273.     Parent = &(RootPtr->root);
  274.   ReplaceNode( Parent, Node1, dummy_p );
  275.  
  276.   /* Swap Node 1 with Node 2, placing Node 1 back into the tree. */
  277.   if( Node2->Link[ubi_trPARENT] )
  278.     Parent = &((Node2->Link[ubi_trPARENT])->Link[(int)(Node2->gender)]);
  279.   else
  280.     Parent = &(RootPtr->root);
  281.   ReplaceNode( Parent, Node2, Node1 );
  282.  
  283.   /* Swap Node 2 and the dummy, thus placing Node 2 back into the tree. */
  284.   if( dummy_p->Link[ubi_trPARENT] )
  285.     Parent = &((dummy_p->Link[ubi_trPARENT])->Link[(int)(dummy_p->gender)]);
  286.   else
  287.     Parent = &(RootPtr->root);
  288.   ReplaceNode( Parent, dummy_p, Node2 );
  289.   } /* SwapNodes */
  290.  
  291. /* -------------------------------------------------------------------------- **
  292.  * These routines allow you to walk through the tree, forwards or backwards.
  293.  */
  294.  
  295. static ubi_btNodePtr SubSlide( register ubi_btNodePtr P,
  296.                                register int           whichway )
  297.   /* ------------------------------------------------------------------------ **
  298.    * Slide down the side of a subtree.
  299.    *
  300.    * Given a starting node, this function returns a pointer to the LEFT-, or
  301.    * RIGHT-most descendent, *or* (if whichway is PARENT) to the tree root.
  302.    *
  303.    *  Input:  P         - a pointer to a starting place.
  304.    *          whichway  - the direction (LEFT, RIGHT, or PARENT) in which to
  305.    *                      travel.
  306.    *  Output: A pointer to a node that is either the root, or has no
  307.    *          whichway-th child but is within the subtree of P.  Note that
  308.    *          the return value may be the same as P.  The return value *will
  309.    *          be* NULL if P is NULL.
  310.    * ------------------------------------------------------------------------ **
  311.    */
  312.   {
  313.   ubi_btNodePtr Q = NULL;
  314.  
  315.   while( P )
  316.     {
  317.     Q = P;
  318.     P = P->Link[ whichway ];
  319.     }
  320.   return( Q );
  321.   } /* SubSlide */
  322.  
  323. static ubi_btNodePtr Neighbor( register ubi_btNodePtr P,
  324.                                register int           whichway )
  325.   /* ------------------------------------------------------------------------ **
  326.    * Given starting point p, return the (key order) next or preceeding node
  327.    * in the tree.
  328.    *
  329.    *  Input:  P         - Pointer to our starting place node.
  330.    *          whichway  - the direction in which to travel to find the
  331.    *                      neighbor, i.e., the RIGHT neighbor or the LEFT
  332.    *                      neighbor.
  333.    *
  334.    *  Output: A pointer to the neighboring node, or NULL if P was NULL.
  335.    *
  336.    *  Notes:  If whichway is PARENT, the results are unpredictable.
  337.    * ------------------------------------------------------------------------ **
  338.    */
  339.   {
  340.   if( P )
  341.     {
  342.     if( P->Link[ whichway ] )
  343.       return( SubSlide( P->Link[ whichway ], (char)ubi_trRevWay(whichway) ) );
  344.     else
  345.       while( P->Link[ ubi_trPARENT ] )
  346.         {
  347.         if( (P->Link[ ubi_trPARENT ])->Link[ whichway ] == P )
  348.           P = P->Link[ ubi_trPARENT ];
  349.         else
  350.           return( P->Link[ ubi_trPARENT ] );
  351.         }
  352.     }
  353.   return( NULL );
  354.   } /* Neighbor */
  355.  
  356. static ubi_btNodePtr Border( ubi_btRootPtr RootPtr,
  357.                              ubi_btItemPtr FindMe,
  358.                              ubi_btNodePtr p,
  359.                              int           whichway )
  360.   /* ------------------------------------------------------------------------ **
  361.    * Given starting point p, which has a key value equal to *FindMe, locate
  362.    * the first (index order) node with the same key value.
  363.    *
  364.    * This function is useful in trees that have can have duplicate keys.
  365.    * For example, consider the following tree:
  366.    *     Tree                                                      Traversal
  367.    *       2    If <p> points to the root and <whichway> is RIGHT,     3
  368.    *      / \    then the return value will be a pointer to the       / \
  369.    *     2   2    RIGHT child of the root node.  The tree on         2   5
  370.    *    /   / \    the right shows the order of traversal.          /   / \
  371.    *   1   2   3                                                   1   4   6
  372.    *
  373.    *  Input:  RootPtr   - Pointer to the tree root structure.
  374.    *          FindMe    - Key value for comparisons.
  375.    *          p         - Pointer to the starting-point node.
  376.    *          whichway  - the direction in which to travel to find the
  377.    *                      neighbor, i.e., the RIGHT neighbor or the LEFT
  378.    *                      neighbor.
  379.    *
  380.    *  Output: A pointer to the first (index, or "traversal", order) node with
  381.    *          a Key value that matches *FindMe.
  382.    *
  383.    *  Notes:  If whichway is PARENT, or if the tree does not allow duplicate
  384.    *          keys, this function will return <p>.
  385.    * ------------------------------------------------------------------------ **
  386.    */
  387.   {
  388.   register ubi_btNodePtr q;
  389.  
  390.   /* Exit if there's nothing that can be done. */
  391.   if( !ubi_trDups_OK( RootPtr ) || (ubi_trPARENT == whichway) )
  392.     return( p );
  393.  
  394.   /* First, if needed, move up the tree.  We need to get to the root of the
  395.    * subtree that contains all of the matching nodes.
  396.    */
  397.   q = p->Link[ubi_trPARENT];
  398.   while( q && (ubi_trEQUAL == ubi_trAbNormal( (*(RootPtr->cmp))(FindMe, q) )) )
  399.     {
  400.     p = q;
  401.     q = p->Link[ubi_trPARENT];
  402.     }
  403.  
  404.   /* Next, move back down in the "whichway" direction. */
  405.   q = p->Link[whichway];
  406.   while( q )
  407.     {
  408.     q = qFind( RootPtr->cmp, FindMe, q );
  409.     if( q )
  410.       {
  411.       p = q;
  412.       q = p->Link[whichway];
  413.       }
  414.     }
  415.   return( p );
  416.   } /* Border */
  417.  
  418.  
  419. /* ========================================================================== **
  420.  * Exported utilities.
  421.  */
  422.  
  423. long ubi_btSgn( register long x )
  424.   /* ------------------------------------------------------------------------ **
  425.    * Return the sign of x; {negative,zero,positive} ==> {-1, 0, 1}.
  426.    *
  427.    *  Input:  x - a signed long integer value.
  428.    *
  429.    *  Output: the "sign" of x, represented as follows:
  430.    *            -1 == negative
  431.    *             0 == zero (no sign)
  432.    *             1 == positive
  433.    *
  434.    * Note: This utility is provided in order to facilitate the conversion
  435.    *       of C comparison function return values into BinTree direction
  436.    *       values: {LEFT, PARENT, EQUAL}.  It is INCORPORATED into the
  437.    *       ubi_trAbNormal() conversion macro!
  438.    *
  439.    * ------------------------------------------------------------------------ **
  440.    */
  441.   {
  442.   return( (x)?((x>0)?(1):(-1)):(0) );
  443.   } /* ubi_btSgn */
  444.  
  445. ubi_btNodePtr ubi_btInitNode( ubi_btNodePtr NodePtr )
  446.   /* ------------------------------------------------------------------------ **
  447.    * Initialize a tree node.
  448.    *
  449.    *  Input:  a pointer to a ubi_btNode structure to be initialized.
  450.    *  Output: a pointer to the initialized ubi_btNode structure (ie. the
  451.    *          same as the input pointer).
  452.    * ------------------------------------------------------------------------ **
  453.    */
  454.   {
  455.   NodePtr->Link[ ubi_trLEFT ]   = NULL;
  456.   NodePtr->Link[ ubi_trPARENT ] = NULL;
  457.   NodePtr->Link[ ubi_trRIGHT ]  = NULL;
  458.   NodePtr->gender               = ubi_trEQUAL;
  459.   return( NodePtr );
  460.   } /* ubi_btInitNode */
  461.  
  462. ubi_btRootPtr ubi_btInitTree( ubi_btRootPtr   RootPtr,
  463.                               ubi_btCompFunc  CompFunc,
  464.                               unsigned char   Flags )
  465.   /* ------------------------------------------------------------------------ **
  466.    * Initialize the fields of a Tree Root header structure.
  467.    *
  468.    *  Input:   RootPtr   - a pointer to an ubi_btRoot structure to be
  469.    *                       initialized.
  470.    *           CompFunc  - a pointer to a comparison function that will be used
  471.    *                       whenever nodes in the tree must be compared against
  472.    *                       outside values.
  473.    *           Flags     - One bytes worth of flags.  Flags include
  474.    *                       ubi_trOVERWRITE and ubi_trDUPKEY.  See the header
  475.    *                       file for more info.
  476.    *
  477.    *  Output:  a pointer to the initialized ubi_btRoot structure (ie. the
  478.    *           same value as RootPtr).
  479.    *
  480.    *  Note:    The interface to this function has changed from that of
  481.    *           previous versions.  The <Flags> parameter replaces two
  482.    *           boolean parameters that had the same basic effect.
  483.    *
  484.    * ------------------------------------------------------------------------ **
  485.    */
  486.   {
  487.   if( RootPtr )
  488.     {
  489.     RootPtr->root   = NULL;
  490.     RootPtr->count  = 0L;
  491.     RootPtr->cmp    = CompFunc;
  492.     RootPtr->flags  = (Flags & ubi_trDUPKEY) ? ubi_trDUPKEY : Flags;
  493.     }                 /* There are only two supported flags, and they are
  494.                        * mutually exclusive.  ubi_trDUPKEY takes precedence
  495.                        * over ubi_trOVERWRITE.
  496.                        */
  497.   return( RootPtr );
  498.   } /* ubi_btInitTree */
  499.  
  500. ubi_trBool ubi_btInsert( ubi_btRootPtr  RootPtr,
  501.                          ubi_btNodePtr  NewNode,
  502.                          ubi_btItemPtr  ItemPtr,
  503.                          ubi_btNodePtr *OldNode )
  504.   /* ------------------------------------------------------------------------ **
  505.    * This function uses a non-recursive algorithm to add a new element to the
  506.    * tree.
  507.    *
  508.    *  Input:   RootPtr  -  a pointer to the ubi_btRoot structure that indicates
  509.    *                       the root of the tree to which NewNode is to be added.
  510.    *           NewNode  -  a pointer to an ubi_btNode structure that is NOT
  511.    *                       part of any tree.
  512.    *           ItemPtr  -  A pointer to the sort key that is stored within
  513.    *                       *NewNode.  ItemPtr MUST point to information stored
  514.    *                       in *NewNode or an EXACT DUPLICATE.  The key data
  515.    *                       indicated by ItemPtr is used to place the new node
  516.    *                       into the tree.
  517.    *           OldNode  -  a pointer to an ubi_btNodePtr.  When searching
  518.    *                       the tree, a duplicate node may be found.  If
  519.    *                       duplicates are allowed, then the new node will
  520.    *                       be simply placed into the tree.  If duplicates
  521.    *                       are not allowed, however, then one of two things
  522.    *                       may happen.
  523.    *                       1) if overwritting *is not* allowed, this
  524.    *                          function will return FALSE (indicating that
  525.    *                          the new node could not be inserted), and
  526.    *                          *OldNode will point to the duplicate that is
  527.    *                          still in the tree.
  528.    *                       2) if overwritting *is* allowed, then this
  529.    *                          function will swap **OldNode for *NewNode.
  530.    *                          In this case, *OldNode will point to the node
  531.    *                          that was removed (thus allowing you to free
  532.    *                          the node).
  533.    *                          **  If you are using overwrite mode, ALWAYS  **
  534.    *                          ** check the return value of this parameter! **
  535.    *                 Note: You may pass NULL in this parameter, the
  536.    *                       function knows how to cope.  If you do this,
  537.    *                       however, there will be no way to return a
  538.    *                       pointer to an old (ie. replaced) node (which is
  539.    *                       a problem if you are using overwrite mode).
  540.    *
  541.    *  Output:  a boolean value indicating success or failure.  The function
  542.    *           will return FALSE if the node could not be added to the tree.
  543.    *           Such failure will only occur if duplicates are not allowed,
  544.    *           nodes cannot be overwritten, AND a duplicate key was found
  545.    *           within the tree.
  546.    * ------------------------------------------------------------------------ **
  547.    */
  548.   {
  549.   ubi_btNodePtr OtherP,
  550.                 parent = NULL;
  551.   char          tmp;
  552.  
  553.   if( !(OldNode) )       /* If they didn't give us a pointer, supply our own. */
  554.     OldNode = &OtherP;
  555.  
  556.   (void)ubi_btInitNode( NewNode );     /* Init the new node's BinTree fields. */
  557.  
  558.   /* Find a place for the new node. */
  559.   *OldNode = TreeFind(ItemPtr, (RootPtr->root), &parent, &tmp, (RootPtr->cmp));
  560.  
  561.   /* Now add the node to the tree... */
  562.   if (!(*OldNode)) /* The easy one: we have a space for a new node! */
  563.     {
  564.     if (!(parent))
  565.       RootPtr->root = NewNode;
  566.     else
  567.       {
  568.       parent->Link[(int)tmp]      = NewNode;
  569.       NewNode->Link[ubi_trPARENT] = parent;
  570.       NewNode->gender             = tmp;
  571.       }
  572.     (RootPtr->count)++;
  573.     return( ubi_trTRUE );
  574.     }
  575.  
  576.   /* If we reach this point, we know that a duplicate node exists.  This
  577.    * section adds the node to the tree if duplicate keys are allowed.
  578.    */
  579.   if( ubi_trDups_OK(RootPtr) )    /* Key exists, add duplicate */
  580.     {
  581.     ubi_btNodePtr q;
  582.  
  583.     tmp = ubi_trRIGHT;
  584.     q = (*OldNode);
  585.     *OldNode = NULL;
  586.     while( q )
  587.       {
  588.       parent = q;
  589.       if( tmp == ubi_trEQUAL )
  590.         tmp = ubi_trRIGHT;
  591.       q = q->Link[(int)tmp];
  592.       if ( q )
  593.         tmp = ubi_trAbNormal( (*(RootPtr->cmp))(ItemPtr, q) );
  594.       }
  595.     parent->Link[(int)tmp]       = NewNode;
  596.     NewNode->Link[ubi_trPARENT]  = parent;
  597.     NewNode->gender              = tmp;
  598.     (RootPtr->count)++;
  599.     return( ubi_trTRUE );
  600.     }
  601.  
  602.   /* If we get to *this* point, we know that we are not allowed to have
  603.    * duplicate nodes, but our node keys match, so... may we replace the
  604.    * old one?
  605.    */
  606.   if( ubi_trOvwt_OK(RootPtr) )    /* Key exists, we replace */
  607.     {
  608.     if (!(parent))
  609.       ReplaceNode( &(RootPtr->root), *OldNode, NewNode );
  610.     else
  611.       ReplaceNode( &(parent->Link[(int)((*OldNode)->gender)]),
  612.                    *OldNode, NewNode );
  613.     return( ubi_trTRUE );
  614.     }
  615.  
  616.   return( ubi_trFALSE );      /* Failure: could not replace an existing node. */
  617.   } /* ubi_btInsert */
  618.  
  619. ubi_btNodePtr ubi_btRemove( ubi_btRootPtr RootPtr,
  620.                             ubi_btNodePtr DeadNode )
  621.   /* ------------------------------------------------------------------------ **
  622.    * This function removes the indicated node from the tree.
  623.    *
  624.    *  Input:   RootPtr  -  A pointer to the header of the tree that contains
  625.    *                       the node to be removed.
  626.    *           DeadNode -  A pointer to the node that will be removed.
  627.    *
  628.    *  Output:  This function returns a pointer to the node that was removed
  629.    *           from the tree (ie. the same as DeadNode).
  630.    *
  631.    *  Note:    The node MUST be in the tree indicated by RootPtr.  If not,
  632.    *           strange and evil things will happen to your trees.
  633.    * ------------------------------------------------------------------------ **
  634.    */
  635.   {
  636.   ubi_btNodePtr p,
  637.                *parentp;
  638.   int           tmp;
  639.  
  640.   /* if the node has both left and right subtrees, then we have to swap
  641.    * it with another node.  The other node we choose will be the Prev()ious
  642.    * node, which is garunteed to have no RIGHT child.
  643.    */
  644.   if( (DeadNode->Link[ubi_trLEFT]) && (DeadNode->Link[ubi_trRIGHT]) )
  645.     SwapNodes( RootPtr, DeadNode, ubi_btPrev( DeadNode ) );
  646.  
  647.   /* The parent of the node to be deleted may be another node, or it may be
  648.    * the root of the tree.  Since we're not sure, it's best just to have
  649.    * a pointer to the parent pointer, whatever it is.
  650.    */
  651.   if (DeadNode->Link[ubi_trPARENT])
  652.     parentp = &((DeadNode->Link[ubi_trPARENT])->Link[(int)(DeadNode->gender)]);
  653.   else
  654.     parentp = &( RootPtr->root );
  655.  
  656.   /* Now link the parent to the only grand-child and patch up the gender. */
  657.   tmp = ((DeadNode->Link[ubi_trLEFT])?ubi_trLEFT:ubi_trRIGHT);
  658.  
  659.   p = (DeadNode->Link[tmp]);
  660.   if( p )
  661.     {
  662.     p->Link[ubi_trPARENT] = DeadNode->Link[ubi_trPARENT];
  663.     p->gender       = DeadNode->gender;
  664.     }
  665.   (*parentp) = p;
  666.  
  667.   /* Finished, reduce the node count and return. */
  668.   (RootPtr->count)--;
  669.   return( DeadNode );
  670.   } /* ubi_btRemove */
  671.  
  672. ubi_btNodePtr ubi_btLocate( ubi_btRootPtr RootPtr,
  673.                             ubi_btItemPtr FindMe,
  674.                             ubi_trCompOps CompOp )
  675.   /* ------------------------------------------------------------------------ **
  676.    * The purpose of ubi_btLocate() is to find a node or set of nodes given
  677.    * a target value and a "comparison operator".  The Locate() function is
  678.    * more flexible and (in the case of trees that may contain dupicate keys)
  679.    * more precise than the ubi_btFind() function.  The latter is faster,
  680.    * but it only searches for exact matches and, if the tree contains
  681.    * duplicates, Find() may return a pointer to any one of the duplicate-
  682.    * keyed records.
  683.    *
  684.    *  Input:
  685.    *     RootPtr  -  A pointer to the header of the tree to be searched.
  686.    *     FindMe   -  An ubi_btItemPtr that indicates the key for which to
  687.    *                 search.
  688.    *     CompOp   -  One of the following:
  689.    *                    CompOp     Return a pointer to the node with
  690.    *                    ------     ---------------------------------
  691.    *                   ubi_trLT - the last key value that is less
  692.    *                              than FindMe.
  693.    *                   ubi_trLE - the first key matching FindMe, or
  694.    *                              the last key that is less than
  695.    *                              FindMe.
  696.    *                   ubi_trEQ - the first key matching FindMe.
  697.    *                   ubi_trGE - the first key matching FindMe, or the
  698.    *                              first key greater than FindMe.
  699.    *                   ubi_trGT - the first key greater than FindMe.
  700.    *  Output:
  701.    *     A pointer to the node matching the criteria listed above under
  702.    *     CompOp, or NULL if no node matched the criteria.
  703.    *
  704.    *  Notes:
  705.    *     In the case of trees with duplicate keys, Locate() will behave as
  706.    *     follows:
  707.    *
  708.    *     Find:  3                       Find: 3
  709.    *     Keys:  1 2 2 2 3 3 3 3 3 4 4   Keys: 1 1 2 2 2 4 4 5 5 5 6
  710.    *                  ^ ^         ^                   ^ ^
  711.    *                 LT EQ        GT                 LE GE
  712.    *
  713.    *     That is, when returning a pointer to a node with a key that is LESS
  714.    *     THAN the target key (FindMe), Locate() will return a pointer to the
  715.    *     LAST matching node.
  716.    *     When returning a pointer to a node with a key that is GREATER
  717.    *     THAN the target key (FindMe), Locate() will return a pointer to the
  718.    *     FIRST matching node.
  719.    *
  720.    *  See Also: ubi_btFind(), ubi_btFirstOf(), ubi_btLastOf().
  721.    * ------------------------------------------------------------------------ **
  722.    */
  723.   {
  724.   register ubi_btNodePtr p;
  725.   ubi_btNodePtr   parent;
  726.   char            whichkid;
  727.  
  728.   /* Start by searching for a matching node. */
  729.   p = TreeFind( FindMe,
  730.                 RootPtr->root,
  731.                 &parent,
  732.                 &whichkid,
  733.                 RootPtr->cmp );
  734.  
  735.   if( p )   /* If we have found a match, we can resolve as follows: */
  736.     {
  737.     switch( CompOp )
  738.       {
  739.       case ubi_trLT:            /* It's just a jump to the left...  */
  740.         p = Border( RootPtr, FindMe, p, ubi_trLEFT );
  741.         return( Neighbor( p, ubi_trLEFT ) );
  742.       case ubi_trGT:            /* ...and then a jump to the right. */
  743.         p = Border( RootPtr, FindMe, p, ubi_trRIGHT );
  744.         return( Neighbor( p, ubi_trRIGHT ) );
  745.       default:
  746.         p = Border( RootPtr, FindMe, p, ubi_trLEFT );
  747.         return( p );
  748.       }
  749.     }
  750.  
  751.   /* Else, no match. */
  752.   if( ubi_trEQ == CompOp )    /* If we were looking for an exact match... */
  753.     return( NULL );           /* ...forget it.                            */
  754.  
  755.   /* We can still return a valid result for GT, GE, LE, and LT.
  756.    * <parent> points to a node with a value that is either just before or
  757.    * just after the target value.
  758.    * Remaining possibilities are LT and GT (including LE & GE).
  759.    */
  760.   if( (ubi_trLT == CompOp) || (ubi_trLE == CompOp) )
  761.     return( (ubi_trLEFT == whichkid) ? Neighbor( parent, whichkid ) : parent );
  762.   else
  763.     return( (ubi_trRIGHT == whichkid) ? Neighbor( parent, whichkid ) : parent );
  764.   } /* ubi_btLocate */
  765.  
  766. ubi_btNodePtr ubi_btFind( ubi_btRootPtr RootPtr,
  767.                           ubi_btItemPtr FindMe )
  768.   /* ------------------------------------------------------------------------ **
  769.    * This function performs a non-recursive search of a tree for any node
  770.    * matching a specific key.
  771.    *
  772.    *  Input:
  773.    *     RootPtr  -  a pointer to the header of the tree to be searched.
  774.    *     FindMe   -  a pointer to the key value for which to search.
  775.    *
  776.    *  Output:
  777.    *     A pointer to a node with a key that matches the key indicated by
  778.    *     FindMe, or NULL if no such node was found.
  779.    *
  780.    *  Note:   In a tree that allows duplicates, the pointer returned *might
  781.    *          not* point to the (sequentially) first occurance of the
  782.    *          desired key.  In such a tree, it may be more useful to use
  783.    *          ubi_btLocate().
  784.    * ------------------------------------------------------------------------ **
  785.    */
  786.   {
  787.   return( qFind( RootPtr->cmp, FindMe, RootPtr->root ) );
  788.   } /* ubi_btFind */
  789.  
  790. ubi_btNodePtr ubi_btNext( ubi_btNodePtr P )
  791.   /* ------------------------------------------------------------------------ **
  792.    * Given the node indicated by P, find the (sorted order) Next node in the
  793.    * tree.
  794.    *  Input:   P  -  a pointer to a node that exists in a binary tree.
  795.    *  Output:  A pointer to the "next" node in the tree, or NULL if P pointed
  796.    *           to the "last" node in the tree or was NULL.
  797.    * ------------------------------------------------------------------------ **
  798.    */
  799.   {
  800.   return( Neighbor( P, ubi_trRIGHT ) );
  801.   } /* ubi_btNext */
  802.  
  803. ubi_btNodePtr ubi_btPrev( ubi_btNodePtr P )
  804.   /* ------------------------------------------------------------------------ **
  805.    * Given the node indicated by P, find the (sorted order) Previous node in
  806.    * the tree.
  807.    *  Input:   P  -  a pointer to a node that exists in a binary tree.
  808.    *  Output:  A pointer to the "previous" node in the tree, or NULL if P
  809.    *           pointed to the "first" node in the tree or was NULL.
  810.    * ------------------------------------------------------------------------ **
  811.    */
  812.   {
  813.   return( Neighbor( P, ubi_trLEFT ) );
  814.   } /* ubi_btPrev */
  815.  
  816. ubi_btNodePtr ubi_btFirst( ubi_btNodePtr P )
  817.   /* ------------------------------------------------------------------------ **
  818.    * Given the node indicated by P, find the (sorted order) First node in the
  819.    * subtree of which *P is the root.
  820.    *  Input:   P  -  a pointer to a node that exists in a binary tree.
  821.    *  Output:  A pointer to the "first" node in a subtree that has *P as its
  822.    *           root.  This function will return NULL only if P is NULL.
  823.    *  Note:    In general, you will be passing in the value of the root field
  824.    *           of an ubi_btRoot structure.
  825.    * ------------------------------------------------------------------------ **
  826.    */
  827.   {
  828.   return( SubSlide( P, ubi_trLEFT ) );
  829.   } /* ubi_btFirst */
  830.  
  831. ubi_btNodePtr ubi_btLast( ubi_btNodePtr P )
  832.   /* ------------------------------------------------------------------------ **
  833.    * Given the node indicated by P, find the (sorted order) Last node in the
  834.    * subtree of which *P is the root.
  835.    *  Input:   P  -  a pointer to a node that exists in a binary tree.
  836.    *  Output:  A pointer to the "last" node in a subtree that has *P as its
  837.    *           root.  This function will return NULL only if P is NULL.
  838.    *  Note:    In general, you will be passing in the value of the root field
  839.    *           of an ubi_btRoot structure.
  840.    * ------------------------------------------------------------------------ **
  841.    */
  842.   {
  843.   return( SubSlide( P, ubi_trRIGHT ) );
  844.   } /* ubi_btLast */
  845.  
  846. ubi_btNodePtr ubi_btFirstOf( ubi_btRootPtr RootPtr,
  847.                              ubi_btItemPtr MatchMe,
  848.                              ubi_btNodePtr p )
  849.   /* ------------------------------------------------------------------------ **
  850.    * Given a tree that a allows duplicate keys, and a pointer to a node in
  851.    * the tree, this function will return a pointer to the first (traversal
  852.    * order) node with the same key value.
  853.    *
  854.    *  Input:  RootPtr - A pointer to the root of the tree.
  855.    *          MatchMe - A pointer to the key value.  This should probably
  856.    *                    point to the key within node *p.
  857.    *          p       - A pointer to a node in the tree.
  858.    *  Output: A pointer to the first node in the set of nodes with keys
  859.    *          matching <FindMe>.
  860.    *  Notes:  Node *p MUST be in the set of nodes with keys matching
  861.    *          <FindMe>.  If not, this function will return NULL.
  862.    * ------------------------------------------------------------------------ **
  863.    */
  864.   {
  865.   /* If our starting point is invalid, return NULL. */
  866.   if( !p || ubi_trAbNormal( (*(RootPtr->cmp))( MatchMe, p ) != ubi_trEQUAL ) )
  867.     return( NULL );
  868.   return( Border( RootPtr, MatchMe, p, ubi_trLEFT ) );
  869.   } /* ubi_btFirstOf */
  870.  
  871. ubi_btNodePtr ubi_btLastOf( ubi_btRootPtr RootPtr,
  872.                             ubi_btItemPtr MatchMe,
  873.                             ubi_btNodePtr p )
  874.   /* ------------------------------------------------------------------------ **
  875.    * Given a tree that a allows duplicate keys, and a pointer to a node in
  876.    * the tree, this function will return a pointer to the last (traversal
  877.    * order) node with the same key value.
  878.    *
  879.    *  Input:  RootPtr - A pointer to the root of the tree.
  880.    *          MatchMe - A pointer to the key value.  This should probably
  881.    *                    point to the key within node *p.
  882.    *          p       - A pointer to a node in the tree.
  883.    *  Output: A pointer to the last node in the set of nodes with keys
  884.    *          matching <FindMe>.
  885.    *  Notes:  Node *p MUST be in the set of nodes with keys matching
  886.    *          <FindMe>.  If not, this function will return NULL.
  887.    * ------------------------------------------------------------------------ **
  888.    */
  889.   {
  890.   /* If our starting point is invalid, return NULL. */
  891.   if( !p || ubi_trAbNormal( (*(RootPtr->cmp))( MatchMe, p ) != ubi_trEQUAL ) )
  892.     return( NULL );
  893.   return( Border( RootPtr, MatchMe, p, ubi_trRIGHT ) );
  894.   } /* ubi_btLastOf */
  895.  
  896. ubi_trBool ubi_btTraverse( ubi_btRootPtr   RootPtr,
  897.                            ubi_btActionRtn EachNode,
  898.                            void           *UserData )
  899.   /* ------------------------------------------------------------------------ **
  900.    * Traverse a tree in sorted order (non-recursively).  At each node, call
  901.    * (*EachNode)(), passing a pointer to the current node, and UserData as the
  902.    * second parameter.
  903.    *  Input:   RootPtr  -  a pointer to an ubi_btRoot structure that indicates
  904.    *                       the tree to be traversed.
  905.    *           EachNode -  a pointer to a function to be called at each node
  906.    *                       as the node is visited.
  907.    *           UserData -  a generic pointer that may point to anything that
  908.    *                       you choose.
  909.    *  Output:  A boolean value.  FALSE if the tree is empty, otherwise TRUE.
  910.    * ------------------------------------------------------------------------ **
  911.    */
  912.   {
  913.   ubi_btNodePtr p;
  914.  
  915.   if( !(p = ubi_btFirst( RootPtr->root )) ) return( ubi_trFALSE );
  916.  
  917.   while( p )
  918.     {
  919.     EachNode( p, UserData );
  920.     p = ubi_btNext( p );
  921.     }
  922.   return( ubi_trTRUE );
  923.   } /* ubi_btTraverse */
  924.  
  925. ubi_trBool ubi_btKillTree( ubi_btRootPtr     RootPtr,
  926.                            ubi_btKillNodeRtn FreeNode )
  927.   /* ------------------------------------------------------------------------ **
  928.    * Delete an entire tree (non-recursively) and reinitialize the ubi_btRoot
  929.    * structure.  Note that this function will return FALSE if either parameter
  930.    * is NULL.
  931.    *
  932.    *  Input:   RootPtr  -  a pointer to an ubi_btRoot structure that indicates
  933.    *                       the root of the tree to delete.
  934.    *           FreeNode -  a function that will be called for each node in the
  935.    *                       tree to deallocate the memory used by the node.
  936.    *
  937.    *  Output:  A boolean value.  FALSE if either input parameter was NULL, else
  938.    *           TRUE.
  939.    *
  940.    * ------------------------------------------------------------------------ **
  941.    */
  942.   {
  943.   ubi_btNodePtr p, q;
  944.  
  945.   if( !(RootPtr) || !(FreeNode) )
  946.     return( ubi_trFALSE );
  947.  
  948.   p = ubi_btFirst( RootPtr->root );
  949.   while( p )
  950.     {
  951.     q = p;
  952.     while( q->Link[ubi_trRIGHT] )
  953.       q = SubSlide( q->Link[ubi_trRIGHT], ubi_trLEFT );
  954.     p = q->Link[ubi_trPARENT];
  955.     if( p )
  956.       p->Link[ ((p->Link[ubi_trLEFT] == q)?ubi_trLEFT:ubi_trRIGHT) ] = NULL;
  957.     FreeNode((void *)q);
  958.     }
  959.  
  960.   (void)ubi_btInitTree( RootPtr,
  961.                         RootPtr->cmp,
  962.                         RootPtr->flags );
  963.   return( ubi_trTRUE );
  964.   } /* ubi_btKillTree */
  965.  
  966. ubi_btNodePtr ubi_btLeafNode( ubi_btNodePtr leader )
  967.   /* ------------------------------------------------------------------------ **
  968.    * Returns a pointer to a leaf node.
  969.    *
  970.    *  Input:  leader  - Pointer to a node at which to start the descent.
  971.    *
  972.    *  Output: A pointer to a leaf node selected in a somewhat arbitrary
  973.    *          manner.
  974.    *
  975.    *  Notes:  I wrote this function because I was using splay trees as a
  976.    *          database cache.  The cache had a maximum size on it, and I
  977.    *          needed a way of choosing a node to sacrifice if the cache
  978.    *          became full.  In a splay tree, less recently accessed nodes
  979.    *          tend toward the bottom of the tree, meaning that leaf nodes
  980.    *          are good candidates for removal.  (I really can't think of
  981.    *          any other reason to use this function.)
  982.    *        + In a simple binary tree or an AVL tree, the most recently
  983.    *          added nodes tend to be nearer the bottom, making this a *bad*
  984.    *          way to choose which node to remove from the cache.
  985.    *        + Randomizing the traversal order is probably a good idea.  You
  986.    *          can improve the randomization of leaf node selection by passing
  987.    *          in pointers to nodes other than the root node each time.  A
  988.    *          pointer to any node in the tree will do.  Of course, if you
  989.    *          pass a pointer to a leaf node you'll get the same thing back.
  990.    *
  991.    * ------------------------------------------------------------------------ **
  992.    */
  993.   {
  994.   ubi_btNodePtr follower = NULL;
  995.   int           whichway = ubi_trLEFT;
  996.  
  997.   while( NULL != leader )
  998.     {
  999.     follower = leader;
  1000.     leader   = follower->Link[ whichway ];
  1001.     if( NULL == leader )
  1002.       {
  1003.       whichway = ubi_trRevWay( whichway );
  1004.       leader   = follower->Link[ whichway ];
  1005.       }
  1006.     }
  1007.  
  1008.   return( follower );
  1009.   } /* ubi_btLeafNode */
  1010.  
  1011. int ubi_btModuleID( int size, char *list[] )
  1012.   /* ------------------------------------------------------------------------ **
  1013.    * Returns a set of strings that identify the module.
  1014.    *
  1015.    *  Input:  size  - The number of elements in the array <list>.
  1016.    *          list  - An array of pointers of type (char *).  This array
  1017.    *                  should, initially, be empty.  This function will fill
  1018.    *                  in the array with pointers to strings.
  1019.    *  Output: The number of elements of <list> that were used.  If this value
  1020.    *          is less than <size>, the values of the remaining elements are
  1021.    *          not guaranteed.
  1022.    *
  1023.    *  Notes:  Please keep in mind that the pointers returned indicate strings
  1024.    *          stored in static memory.  Don't free() them, don't write over
  1025.    *          them, etc.  Just read them.
  1026.    * ------------------------------------------------------------------------ **
  1027.    */
  1028.   {
  1029.   if( size > 0 )
  1030.     {
  1031.     list[0] = ModuleID;
  1032.     if( size > 1 )
  1033.       list[1] = NULL;
  1034.     return( 1 );
  1035.     }
  1036.   return( 0 );
  1037.   } /* ubi_btModuleID */
  1038.  
  1039.  
  1040. /* ========================================================================== */
  1041.